package datastructure.unionfind;

public class UnionFind2 implements UF {

    //实际表示parent[i]指向那个节点
    private int[] parent;

    public UnionFind2(int size) {
        parent = new int[size];
        //初始的时候，parent[i]=i  指向自己
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    @Override
    public int getSize() {

        return parent.length;
    }

    // 查看元素p对饮的集合编号  O(h) h为树的高度
    // parent[i]表示第i个元素指向那个节点
    // 向上查找，直到查到跟节点
    private int find(int p) {
        if (p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is out of bound.");
        while (p != parent[p]) {
            p = parent[p];
        }

        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        // 复杂度分析 查找 logn
        int findP = find(p);
        int findQ = find(q);
        return findP == findQ;
    }

    @Override
    public void unionElements(int p, int q) {
        int parentP = find(p);
        int parentQ = find(q);
        if (parentP == parentQ) {
            return;
        } else {

            parent[parentP] = parentQ;
        }
    }

}
